<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>dijkstra</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="dijkstra">dijkstra</h1>
<p>ijkstra算法一般是用于解决求解最短路径问题，属于盲目搜索算法。
Dijkstra不能处理包含负边的情况。 如果有权重是负数的边，需要Bellman-Ford算法</p>
<p>Dijkstra算法(这个荷兰词真难读。。。不过Dijkstra是一位非常NB的计算机科学家，goto有害论、信号量和PV原语、哲学家聚餐问题、银行家算法等等，都是这位大牛搞出来的)，是有向/无向加权图(就是每条边都有长度)中，计算两个点之间最短距离的有效方法，在使用堆排序的情况下，它的时间复杂度为O(Nlog(N+M))，(这里N代表节点数，M代表边数)很接近线性了，还是非常好的。</p>
<p>不过，Dijkstra算法有一个限制，就是它只适用于边长不为负的图。如果一张图里有负数长的边长，那么Dijkstra算法就不适用了。这时候就需要另外的算法了。</p>
<p>为什么不适用呢？其实很容易就可以找到反例。假设一张加权图，有的边长为负数。假设边长最小为-10，我们把所有的边长都加上10，就这就可以得到一张无负值加权图。此时用Dijkstra算法算出一个从节点s到节点t的最短路径L，L共包括n条边，总长为t；那么对于原图，每条边都要减去10，所以原图中L的长度是t-10*n。这是Diskstra算法算出的结果。</p>
<p>那么问题来了：对于加上10之后的图，假设还有一个从s到t的路径M，长度为t1，它共包括n1条边，比L包含的边长多，那么还原回来之后，每条边需要减去10，那么M的总长就是t1-10<em>n1。那么，是不是M的总长一定比L的总长更长一些呢？不一定。假如n1&gt;n，也就是说M的边数比L的边数更多，那么M减去的要比L减去的更多，那么t1-10</em>n1&lt;t-10*n是可能的。此时Dijkstra算法是不成立的。</p>
<p>另外，还有一种更简单的例子：假如一张图里有一个总长为负数的环，那么Dijkstra算法有可能会沿着这个环一直绕下去，绕到地老天荒。。。</p>
<p>另外，如果一张图里有负数边，但没有总长为负数的环，此时可以用Bellman-Ford算法计算。虽然它比Dijkstra慢了一些，但人家应用范围更广啊。</p>
<p>原理：不断求解起始节点到其他节点的最短路径成本。</p>
<p>First：</p>
<ul>
<li>引入cost字典，表示对于起始点到每一个其他节点的成本。eg:cost[2]=1。表示起始点（这里设定为节点1）到节点2的成本需要1。</li>
<li>引入visted列表，记录已访问的节点。eg:起始visted=[1];</li>
<li>引入Parents字典，记录已求解最短路径节点的前一个节点。eg:假设至3节点的最短路径为1-2-4-3，则parents[3]=4;</li>
</ul>
<pre><code><code><div>current_node = 1 # 起始节点
while :
   针对current出发的每一条路径  current-&gt;target:cost
   new_cost = costs[current] + cost
   old_cost = costs[dst]
   if old_cost 不存在， 或者 new_cost &lt; old_cost:
       costs[target] = costs[current] + cost
       father[target] = current
   visited[current] = True
   current_node = find_next()

其中find_next() 是找出还没被访问过的节点中，costs最小的那个， 如果找不到，则循环结束。
</div></code></code></pre>
<h1 id="1-leetcode-743-network-delay-time">1. leetcode 743. Network Delay Time</h1>
<p><a href="https://leetcode.com/problems/network-delay-time/">https://leetcode.com/problems/network-delay-time/</a></p>
<p>一个有向图，从节点K出发， 需要多长时间才能遍历所有节点。 如果不能遍历所有节点，则返回-1</p>
<pre><code><code><div>Share
There are N network nodes, labelled 1 to N.

Given times, a list of travel times as directed edges times[i] = (u, v, w), where u is the source node, v is the target node, and w is the time it takes for a signal to travel from source to target.

Now, we send a signal from a certain node K. How long will it take for all nodes to receive the signal? If it is impossible, return -1.

</div></code></code></pre>
<h2 id="11-v1-dijkstra-会超时">1.1 v1. dijkstra 会超时</h2>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> heapq
<span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> defaultdict

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">networkDelayTime</span><span class="hljs-params">(self, times: List[List[int]], N: int, K: int)</span> -&gt; int:</span>
        <span class="hljs-string">''' Dijkstra'''</span>
        neighbors = defaultdict(list)
        <span class="hljs-keyword">for</span> n_src, n_dst, n_value <span class="hljs-keyword">in</span> times:
            neighbors[n_src].append((n_dst, n_value))
        distance = {K:<span class="hljs-number">0</span>}
        dp = [(<span class="hljs-number">0</span>,K)]
        visited = {}
        <span class="hljs-keyword">while</span> dp:
            value,node = heapq.heappop(dp)
            visited[node] = <span class="hljs-literal">True</span>
            <span class="hljs-keyword">for</span> n_dst, n_value <span class="hljs-keyword">in</span> neighbors[node]:
                <span class="hljs-keyword">if</span> n_dst <span class="hljs-keyword">in</span> distance:
                    distance[n_dst] = min(distance[n_dst], distance[node] + n_value)
                <span class="hljs-keyword">else</span>:
                    distance[n_dst] = distance[node] + n_value
                <span class="hljs-keyword">if</span> n_dst <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> visited:
                    heapq.heappush(dp, (distance[n_dst], n_dst))
        <span class="hljs-keyword">if</span> len(visited) &lt; N:
            <span class="hljs-keyword">return</span> - <span class="hljs-number">1</span>
        <span class="hljs-keyword">else</span>:
            <span class="hljs-keyword">return</span> max(distance.values())
        
</div></code></pre>
<h2 id="12-v2-dijkstra-查看答案后">1.2 v2 dijkstra 查看答案后</h2>
<ul>
<li><a href="https://leetcode.com/problems/network-delay-time/discuss/187713/Python-concise-queue-and-heap-solutions">https://leetcode.com/problems/network-delay-time/discuss/187713/Python-concise-queue-and-heap-solutions</a></li>
<li>发现不需要visited 字典， 而且判断代码可以大大简化</li>
</ul>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> heapq
<span class="hljs-keyword">from</span> collections <span class="hljs-keyword">import</span> defaultdict

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">networkDelayTime</span><span class="hljs-params">(self, times: List[List[int]], N: int, K: int)</span> -&gt; int:</span>
        <span class="hljs-string">''' Dijkstra'''</span>
        neighbors = defaultdict(list)
        <span class="hljs-keyword">for</span> n_src, n_dst, n_value <span class="hljs-keyword">in</span> times:
            neighbors[n_src].append((n_dst, n_value))
        distance = {}
        dp = [(<span class="hljs-number">0</span>,K)]
        <span class="hljs-keyword">while</span> dp:
            value, node = heapq.heappop(dp)
            <span class="hljs-keyword">if</span> node <span class="hljs-keyword">in</span> distance:
                <span class="hljs-keyword">continue</span>
            distance[node] = value
            <span class="hljs-keyword">for</span> n_dst, n_value <span class="hljs-keyword">in</span> neighbors[node]:
                <span class="hljs-keyword">if</span> n_dst <span class="hljs-keyword">in</span> distance:
                    <span class="hljs-keyword">continue</span>
                heapq.heappush(dp, (value+n_value, n_dst))
        <span class="hljs-keyword">return</span> max(distance.values()) <span class="hljs-keyword">if</span> len(distance) ==  N <span class="hljs-keyword">else</span> <span class="hljs-number">-1</span>            
</div></code></pre>
<h2 id="13-v3-dijkstra">1.3 v3 dijkstra</h2>
<ul>
<li>有人改进了一点，在loop中，发现len(dist)==N 就直接退出</li>
<li>而且由于dijkstra的算法特性，越是后面遍历的点，距离越远。 最后一个遍历的点，一定是距离最大的点。</li>
</ul>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
<span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">networkDelayTime</span><span class="hljs-params">(self, times: List[List[int]], N: int, K: int)</span> -&gt; int:</span>
    dic = collections.defaultdict(list)
    <span class="hljs-keyword">for</span> u,v,w <span class="hljs-keyword">in</span> times:
        dic[u].append((v,w))
    q =  [(<span class="hljs-number">0</span>,K)]
    dist = {}
    <span class="hljs-keyword">while</span> q:
        d, curr = heapq.heappop(q)
        <span class="hljs-keyword">if</span> curr <span class="hljs-keyword">in</span> dist: <span class="hljs-keyword">continue</span>
        dist[curr] = d
        <span class="hljs-keyword">if</span> len(dist) == N: <span class="hljs-keyword">return</span> d
        <span class="hljs-keyword">for</span> target, time <span class="hljs-keyword">in</span> dic[curr]:
            <span class="hljs-keyword">if</span> target <span class="hljs-keyword">not</span> <span class="hljs-keyword">in</span> dist:
                heapq.heappush(q,(time + d,target))
    <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
</div></code></pre>
<h2 id="14-with-queue-spfashort-path-fast-algorithm">1.4 with Queue: SPFA(short path fast algorithm)</h2>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">networkDelayTime</span><span class="hljs-params">(self, times, N, K)</span>:</span>
        t, graph, q = [<span class="hljs-number">0</span>] + [float(<span class="hljs-string">"inf"</span>)] * N, collections.defaultdict(list), collections.deque([(<span class="hljs-number">0</span>, K)])
        <span class="hljs-keyword">for</span> u, v, w <span class="hljs-keyword">in</span> times:
            graph[u].append((v, w))
        <span class="hljs-keyword">while</span> q:
            time, node = q.popleft()
            <span class="hljs-keyword">if</span> time &lt; t[node]:
                t[node] = time
                <span class="hljs-keyword">for</span> v, w <span class="hljs-keyword">in</span> graph[node]:
                    q.append((time + w, v))
        mx = max(t)
        <span class="hljs-keyword">return</span> mx <span class="hljs-keyword">if</span> mx &lt; float(<span class="hljs-string">"inf"</span>) <span class="hljs-keyword">else</span> <span class="hljs-number">-1</span>
</div></code></pre>
<h2 id="15-bellman">1.5 Bellman</h2>
<ul>
<li><a href="https://leetcode.com/problems/network-delay-time/discuss/109982/C%2B%2B-Bellman-Ford">https://leetcode.com/problems/network-delay-time/discuss/109982/C%2B%2B-Bellman-Ford</a></li>
</ul>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">networkDelayTime</span><span class="hljs-params">(self, times: List[List[int]], N: int, K: int)</span> -&gt; int:</span>
        <span class="hljs-string">''' bellman '''</span>

        dp = [float(<span class="hljs-string">'inf'</span>)] * (N+<span class="hljs-number">1</span>)
        dp[K] = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(N):
            <span class="hljs-keyword">for</span> src, dst, time <span class="hljs-keyword">in</span> times:
                dp[dst] = min(dp[dst], dp[src] + time)
        
        ans = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> c <span class="hljs-keyword">in</span> dp[<span class="hljs-number">1</span>:]:
            <span class="hljs-keyword">if</span> c == float(<span class="hljs-string">'inf'</span>):
                <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
            <span class="hljs-keyword">else</span>:
                ans = max(ans, c)
        <span class="hljs-keyword">return</span> ans    
</div></code></pre>
<h1 id="2-778-swim-in-rising-water">2. 778. Swim in Rising Water</h1>
<p>On an N x N grid, each square grid[i][j] represents the elevation at that point (i,j).</p>
<p>Now rain starts to fall. At time t, the depth of the water everywhere is t. You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t. You can swim infinite distance in zero time. Of course, you must stay within the boundaries of the grid during your swim.</p>
<p>You start at the top left square (0, 0). What is the least time until you can reach the bottom right square (N-1, N-1)?</p>
<pre><code><code><div>Example 1:

Input: [[0,2],[1,3]]
Output: 3
Explanation:
At time 0, you are in grid location (0, 0).
You cannot go anywhere else because 4-directionally adjacent neighbors have a higher elevation than t = 0.

You cannot reach point (1, 1) until time 3.
When the depth of water is 3, we can swim anywhere inside the grid.
Example 2:

Input: [[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]
Output: 16
Explanation:
 0  1  2  3  4
24 23 22 21  5
12 13 14 15 16
11 17 18 19 20
10  9  8  7  6

The final route is marked in bold.
We need to wait until time 16 so that (0, 0) and (4, 4) are connected.
Note:

2 &lt;= N &lt;= 50.
grid[i][j] is a permutation of [0, ..., N*N - 1].

https://leetcode.com/problems/swim-in-rising-water/
</div></code></code></pre>
<h1 id="21-a">2.1 A*</h1>
<p>下面是参考了标准答案的贪心算法. 类似于A*, 每次</p>
<ol>
<li>从open set里面找最小的节点(x, y)</li>
<li>遍历open set的合法邻居， 加入open set, 同时标记(x,y)为已访问(放入close set)</li>
</ol>
<p>在遍历过程中记录已经访问过的最大值ans, 如果访问到目标节点就直接返回ans</p>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> heapq

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">swimInWater</span><span class="hljs-params">(self, grid: List[List[int]])</span> -&gt; int:</span>
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">_isvaid</span><span class="hljs-params">(x, y)</span>:</span>
            <span class="hljs-keyword">if</span> x &lt; <span class="hljs-number">0</span> <span class="hljs-keyword">or</span> x &gt;= m <span class="hljs-keyword">or</span> y &lt; <span class="hljs-number">0</span> <span class="hljs-keyword">or</span> y &gt;= n:
                <span class="hljs-keyword">return</span> <span class="hljs-literal">False</span>
            <span class="hljs-keyword">return</span> <span class="hljs-literal">True</span>
                        
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> grid <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> grid[<span class="hljs-number">0</span>]:
            <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
        m = len(grid)
        n = len(grid[<span class="hljs-number">0</span>])

        open_set = [(grid[<span class="hljs-number">0</span>][<span class="hljs-number">0</span>], <span class="hljs-number">0</span>, <span class="hljs-number">0</span>)]
        close_set = [<span class="hljs-number">0</span>] * m * n
        ans = <span class="hljs-number">0</span>        
        <span class="hljs-keyword">while</span> open_set:
            c, x, y = heapq.heappop(open_set)
            ans = max(ans, c)
            <span class="hljs-keyword">if</span> x == m<span class="hljs-number">-1</span> <span class="hljs-keyword">and</span> y == n<span class="hljs-number">-1</span>:
                <span class="hljs-keyword">return</span> ans
            <span class="hljs-keyword">for</span> x_n, y_n <span class="hljs-keyword">in</span> [(<span class="hljs-number">1</span>, <span class="hljs-number">0</span>), (<span class="hljs-number">-1</span>,<span class="hljs-number">0</span>), (<span class="hljs-number">0</span>, <span class="hljs-number">1</span>), (<span class="hljs-number">0</span>, <span class="hljs-number">-1</span>)]:
                x2 = x_n + x
                y2 = y_n + y
                index2 = x2 * n + y2
                <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> _isvaid(x2, y2) <span class="hljs-keyword">or</span> close_set[index2] == <span class="hljs-number">1</span>:
                    <span class="hljs-keyword">continue</span>
                
                heapq.heappush(open_set, (grid[x2][y2], x2, y2))
                close_set[index2] = <span class="hljs-number">1</span>

           
        <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
</div></code></pre>
<h2 id="22-dijkstra">2.2 dijkstra</h2>
<p>20200307， 今天参考了下面787的答案后，写出了和上面一样的代码，哈哈。 但是有一点一样，我压栈的时候，用的是max(c, grid[y2][x2])， 而不是上面的gri[x2][y2], 我的x,y定义也和上面是反的。 其实都是dijkstra算法</p>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> heapq

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">swimInWater</span><span class="hljs-params">(self, grid: List[List[int]])</span> -&gt; int:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> grid <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> grid[<span class="hljs-number">0</span>]:
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
        m = len(grid)
        n = len(grid[<span class="hljs-number">0</span>])
        dp = [(grid[<span class="hljs-number">0</span>][<span class="hljs-number">0</span>], <span class="hljs-number">0</span>, <span class="hljs-number">0</span>)]
        visited = {}
        <span class="hljs-keyword">while</span> dp:
            <span class="hljs-comment">#print(dp)</span>
            c, y, x = heapq.heappop(dp)
            <span class="hljs-keyword">if</span> x == n<span class="hljs-number">-1</span> <span class="hljs-keyword">and</span> y == m<span class="hljs-number">-1</span>:
                <span class="hljs-keyword">return</span> c
            <span class="hljs-keyword">for</span> dx,dy <span class="hljs-keyword">in</span> [(<span class="hljs-number">0</span>,<span class="hljs-number">1</span>), (<span class="hljs-number">0</span>,<span class="hljs-number">-1</span>), (<span class="hljs-number">1</span>,<span class="hljs-number">0</span>), (<span class="hljs-number">-1</span>,<span class="hljs-number">0</span>)]:
                x2 = x + dx
                y2 = y + dy
                <span class="hljs-keyword">if</span> x2 &lt; <span class="hljs-number">0</span> <span class="hljs-keyword">or</span> x2 &gt;=n <span class="hljs-keyword">or</span> y2 &lt; <span class="hljs-number">0</span> <span class="hljs-keyword">or</span> y2 &gt;= m:
                    <span class="hljs-keyword">continue</span>
                <span class="hljs-keyword">if</span> (x2,y2) <span class="hljs-keyword">in</span> visited:
                    <span class="hljs-keyword">continue</span>
                visited[(x2,y2)] = <span class="hljs-number">1</span>
                heapq.heappush(dp, (max(c, grid[y2][x2]), y2, x2))
        <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
</div></code></pre>
<h2 id="23-20200531-今天重新写了一遍去掉了visited-用distance代替">2.3 20200531 今天重新写了一遍，去掉了visited, 用distance代替</h2>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> heapq

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">swimInWater</span><span class="hljs-params">(self, grid: List[List[int]])</span> -&gt; int:</span>
        <span class="hljs-string">'''dijkstra'''</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> grid <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> grid[<span class="hljs-number">0</span>]:
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
        m = len(grid)
        n = len(grid[<span class="hljs-number">0</span>])
        dp = [(grid[<span class="hljs-number">0</span>][<span class="hljs-number">0</span>], <span class="hljs-number">0</span>, <span class="hljs-number">0</span>)]
        distance = {}
        <span class="hljs-keyword">while</span> dp:
            <span class="hljs-comment">#print(dp)</span>
            c, y, x = heapq.heappop(dp)
            <span class="hljs-keyword">if</span> x == n<span class="hljs-number">-1</span> <span class="hljs-keyword">and</span> y == m<span class="hljs-number">-1</span>:
                <span class="hljs-keyword">return</span> c
            <span class="hljs-keyword">if</span> (y,x) <span class="hljs-keyword">in</span> distance:
                <span class="hljs-keyword">continue</span>
            distance[(y,x)] = c
            <span class="hljs-keyword">for</span> dx,dy <span class="hljs-keyword">in</span> [(<span class="hljs-number">0</span>,<span class="hljs-number">1</span>), (<span class="hljs-number">0</span>,<span class="hljs-number">-1</span>), (<span class="hljs-number">1</span>,<span class="hljs-number">0</span>), (<span class="hljs-number">-1</span>,<span class="hljs-number">0</span>)]:
                x2 = x + dx
                y2 = y + dy
                <span class="hljs-keyword">if</span> x2 &lt; <span class="hljs-number">0</span> <span class="hljs-keyword">or</span> x2 &gt;=n <span class="hljs-keyword">or</span> y2 &lt; <span class="hljs-number">0</span> <span class="hljs-keyword">or</span> y2 &gt;= m:
                    <span class="hljs-keyword">continue</span>           
                <span class="hljs-keyword">if</span> (y2,x2) <span class="hljs-keyword">in</span> distance:
                    <span class="hljs-keyword">continue</span>
                heapq.heappush(dp, (max(c, grid[y2][x2]), y2, x2))
        <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
        
</div></code></pre>
<h2 id="24-bellman">2.4 bellman</h2>
<p>会超时。。。</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">swimInWater</span><span class="hljs-params">(self, grid: List[List[int]])</span> -&gt; int:</span>
        <span class="hljs-string">'''bellman'''</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> grid <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> grid[<span class="hljs-number">0</span>]:
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
        m = len(grid)
        n = len(grid[<span class="hljs-number">0</span>])
        dp = [[float(<span class="hljs-string">'inf'</span>)] * n <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(m) ]
        dp[<span class="hljs-number">0</span>][<span class="hljs-number">0</span>] = grid[<span class="hljs-number">0</span>][<span class="hljs-number">0</span>]
        <span class="hljs-keyword">for</span> k <span class="hljs-keyword">in</span> range(m*n):
            <span class="hljs-keyword">for</span> y <span class="hljs-keyword">in</span> range(m):
                <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> range(n):
                    <span class="hljs-keyword">if</span> dp[y][x] == float(<span class="hljs-string">"inf"</span>):
                        <span class="hljs-keyword">continue</span>
                    <span class="hljs-keyword">for</span> dx,dy <span class="hljs-keyword">in</span> [(<span class="hljs-number">0</span>,<span class="hljs-number">1</span>), (<span class="hljs-number">0</span>,<span class="hljs-number">-1</span>), (<span class="hljs-number">1</span>,<span class="hljs-number">0</span>), (<span class="hljs-number">-1</span>,<span class="hljs-number">0</span>)]:
                        x2 = x + dx
                        y2 = y + dy
                        <span class="hljs-keyword">if</span> x2 &lt; <span class="hljs-number">0</span> <span class="hljs-keyword">or</span> x2 &gt;=n <span class="hljs-keyword">or</span> y2 &lt; <span class="hljs-number">0</span> <span class="hljs-keyword">or</span> y2 &gt;= m:
                            <span class="hljs-keyword">continue</span>           
                        <span class="hljs-keyword">if</span> dp[y2][x2] == float(<span class="hljs-string">"inf"</span>):
                            dp[y2][x2] = max(dp[y][x], grid[y2][x2])
                        <span class="hljs-keyword">else</span>:
                            <span class="hljs-keyword">if</span> dp[y2][x2] &gt; grid[y2][x2]:
                                dp[y2][x2] = max(min(dp[y2][x2], dp[y][x]), grid[y2][x2])
        <span class="hljs-keyword">return</span> dp[m<span class="hljs-number">-1</span>][n<span class="hljs-number">-1</span>]
    
</div></code></pre>
<h1 id="3-787-cheapest-flights-within-k-stops">3. 787. Cheapest Flights Within K Stops</h1>
<ul>
<li><a href="https://leetcode.com/problems/cheapest-flights-within-k-stops/">https://leetcode.com/problems/cheapest-flights-within-k-stops/</a></li>
</ul>
<p>这道题可以用dijkstra算法，也可以用bellman算法</p>
<h2 id="31-bellman算法">3.1 bellman算法</h2>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findCheapestPrice</span><span class="hljs-params">(self, n: int, flights: List[List[int]], src: int, dst: int, K: int)</span> -&gt; int:</span>
        dp = [float(<span class="hljs-string">'inf'</span>)] * n
        dp[src] = <span class="hljs-number">0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(K+<span class="hljs-number">1</span>):
            dp2 = dp[:]
            <span class="hljs-keyword">for</span> a,b,p <span class="hljs-keyword">in</span> flights:
                dp2[b] = min(dp2[b], dp[a] + p)
            dp = dp2
        <span class="hljs-keyword">return</span> dp[dst] <span class="hljs-keyword">if</span> dp[dst] &lt;= <span class="hljs-number">1000000</span> <span class="hljs-keyword">else</span> <span class="hljs-number">-1</span>
</div></code></pre>
<h3 id="为什么要用dp2这个临时数组来过渡">为什么要用dp2这个临时数组来过渡？</h3>
<ul>
<li>temp array is needed here since in (i)th iteration, we only want to relax nodes that are reachable from previous (i-1) iteration, this differs from original Bellman-Ford code since now we have within K stops requirement</li>
<li>要注意到转机次数要小于等于k，而对一个点利用所有边进行松弛的时候，会出现利用多条边即多次转机的情况。</li>
</ul>
<p>如下图，如果要求0-&gt;2的最便宜机票，不允许中转(K=0)</p>
<ul>
<li>如果用dp2过渡，可以得到正确答案500</li>
<li>如果不用dp2过渡，则得到错误的答案200</li>
</ul>
<p><img src="file:///e:\gitee\leetcode\graph\pics\bellman1.png" alt="bellman1.png"></p>
<h2 id="32-dijkstra算法">3.2 dijkstra算法</h2>
<pre><code class="language-python"><div><span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findCheapestPrice</span><span class="hljs-params">(self, n, flights, src, dst, k)</span>:</span>
        f = collections.defaultdict(dict)
        <span class="hljs-keyword">for</span> a, b, p <span class="hljs-keyword">in</span> flights:
            f[a][b] = p
        heap = [(<span class="hljs-number">0</span>, src, k + <span class="hljs-number">1</span>)]
        <span class="hljs-keyword">while</span> heap:
            p, i, k = heapq.heappop(heap)
            <span class="hljs-keyword">if</span> i == dst:
                <span class="hljs-keyword">return</span> p
            <span class="hljs-keyword">if</span> k &gt; <span class="hljs-number">0</span>:
                <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> f[i]:
                    heapq.heappush(heap, (p + f[i][j], j, k - <span class="hljs-number">1</span>))
        <span class="hljs-keyword">return</span> <span class="hljs-number">-1</span>
</div></code></pre>
<p>这种利用heqpq来找到下一个检索起始点的思路值得借鉴！</p>
<h1 id="4-bellman">4. bellman</h1>
<ul>
<li><a href="https://zhuanlan.zhihu.com/p/36295603">https://zhuanlan.zhihu.com/p/36295603</a></li>
</ul>
<pre><code><code><div>procedure BellmanFord(list vertices, list edges, vertex source)
   // 该实现读入边和节点的列表，并向两个数组（distance和predecessor）中写入最短路径信息

   // 步骤1：初始化图
   for each vertex v in vertices:
       if v is source then distance[v] := 0
       else distance[v] := infinity
       predecessor[v] := null

   // 步骤2：重复对每一条边进行松弛操作
   for i from 1 to size(vertices)-1:
       for each edge (u, v) with weight w in edges:
           if distance[u] + w &lt; distance[v]:
               distance[v] := distance[u] + w
               predecessor[v] := u

   // 步骤3：检查负权环
   for each edge (u, v) with weight w in edges:
       if distance[u] + w &lt; distance[v]:
           error &quot;图包含了负权环&quot;
</div></code></code></pre>
<p>tushar roy</p>
<ul>
<li><a href="https://www.youtube.com/watch?v=-mOEd_3gTK0&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=7">https://www.youtube.com/watch?v=-mOEd_3gTK0&amp;list=PLrmLmBdmIlpu2f2g8ltqaaCZiq6GJvl1j&amp;index=7</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/BellmanFordShortestPath.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/graph/BellmanFordShortestPath.java</a></li>
</ul>
<p>bellman算法能解决有边是负数的情况，但是如果存在一个环, 它的所有边的权重和是负数，则无法收敛，也会计算失败。</p>
<pre><code class="language-java"><div><span class="hljs-comment">/**
 * Date 11/05/2015
 * <span class="hljs-doctag">@author</span> Tushar Roy
 *
 * Write program for Bellman Ford algorithm to find single source shortest path in directed graph.
 * Bellman ford works with negative edges as well unlike Dijksra's algorithm. If there is negative
 * weight cycle it detects it.
 *
 * Time complexity - O(EV)
 * Space complexity - O(V)
 *
 * References
 * https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm
 * http://www.geeksforgeeks.org/dynamic-programming-set-23-bellman-ford-algorithm/
 */</span>

        <span class="hljs-comment">//relax edges repeatedly V - 1 times</span>
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; V - <span class="hljs-number">1</span> ; i++) {
            <span class="hljs-keyword">for</span> (Edge&lt;Integer&gt; edge : graph.getAllEdges()) {
                Vertex&lt;Integer&gt; u = edge.getVertex1();
                Vertex&lt;Integer&gt; v = edge.getVertex2();
                <span class="hljs-comment">//relax the edge</span>
                <span class="hljs-comment">//if we get better distance to v via u then use this distance</span>
                <span class="hljs-comment">//and set u as parent of v.</span>
                <span class="hljs-keyword">if</span> (distance.get(u) + edge.getWeight() &lt; distance.get(v)) {
                    distance.put(v, distance.get(u) + edge.getWeight());
                    parent.put(v, u);
                }
            }
        }

        <span class="hljs-comment">//relax all edges again. If we still get lesser distance it means</span>
        <span class="hljs-comment">//there is negative weight cycle in the graph. Throw exception in that</span>
        <span class="hljs-comment">//case</span>
        <span class="hljs-keyword">for</span> (Edge&lt;Integer&gt; edge : graph.getAllEdges()) {
            Vertex&lt;Integer&gt; u = edge.getVertex1();
            Vertex&lt;Integer&gt; v = edge.getVertex2();
            <span class="hljs-keyword">if</span> (distance.get(u) + edge.getWeight() &lt; distance.get(v)) {
                <span class="hljs-keyword">throw</span> <span class="hljs-keyword">new</span> NegativeWeightCycleException();
            }
        }
        <span class="hljs-keyword">return</span> distance;
</div></code></pre>
<p>为什么要迭代 len(顶点数目) - 1 次, 这是最坏情况。  最好情况是，只需要迭代一次。见下图</p>
<p><img src="file:///e:\gitee\leetcode\graph\pics\bellman3.png" alt="bellman3.png"></p>
<p>为什么如果有环的权重和是负数，则计算不能收敛。 见下图</p>
<p><img src="file:///e:\gitee\leetcode\graph\pics\bellman2.png" alt="bellman2.png"></p>

    </body>
    </html>